package listnode

import "sort"

func sortList(head *ListNode) *ListNode {
	if head == nil {
		return head
	}
	list := []*ListNode{}
	for head != nil {
		list = append(list, head)
		head = head.Next
	}
	sort.Slice(list, func(i, j int) bool {
		return list[i].Val < list[j].Val
	})
	for i := 0; i < len(list); i++ {
		l := list[i]
		if i != len(list) - 1 {
			l.Next = list[i + 1]
		} else {
			l.Next = nil
		}
	}
	return list[0]
}

type ListNode struct {
	Val  int
	Next *ListNode
}